package leetcode.code0828;

import java.util.Arrays;

public class Solution1 extends Solution828 {

	private static final char A = 'A';
	private int M = (int) 1e9 + 7;

	@Override
	public int uniqueLetterString(String s) {
		int len = s.length();
		int ans = 0;
		char[] chars = s.toCharArray();
		int[] dp = new int[len];
		for (int i = 0; i < len; i++) {
			dp[i] = 1;
			ans += 1;
		}
		int[] d = new int[26];
		for (int row = 1; row < len; row++) {
			int l = len - row - 1;
			int r = len - 2;
			d[chars[l] - A] += 1;
			int[] dic = Arrays.copyOf(d, 26);
			for (int col = len - 1; col >= row; col--) {
				int cur = chars[col] - A;
				if (dic[cur] == 0) {
					dp[col] = dp[col - 1] + 1;
				} else if (dic[cur] == 1) {
					dp[col] = dp[col - 1] - 1;
				} else {
					dp[col] = dp[col - 1];
				}
				ans = (ans + dp[col] + M) % M;
				if (l > 0)
					dic[chars[--l] - A]++;
				dic[chars[r--] - A] -= 1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
